# 变位词的判别
def anagram_solution1(s1: str, s2: str) -> bool:
    """标记法"""
    alist = list(s2)

    pos1 = 0
    still_ok = True

    while pos1 < len(s1) and still_ok:
        pos2 = 0
        found = False
        while pos2 < len(alist) and not found:
            if s1[pos1] == alist[pos2]:
                found = True
            else:
                pos2 = pos2 + 1

        if found:
            alist[pos2] = None
        else:
            still_ok = False

        pos1 = pos1 + 1

    return still_ok


def anagram_solution2(s1: str, s2: str) -> bool:
    """标记法改良版"""
    alist = list(s2)

    for v1 in s1:  # O(n^2)
        found = False
        for k2, v2 in enumerate(alist):
            if v1 == v2:
                alist[k2] = None
                found = True
                break

        if not found:
            return False

    for v in alist:
        if v is not None:
            return False

    return True


def anagram_solution3(s1: str, s2: str) -> bool:
    """排序法"""
    alist1 = list(s1)
    alist2 = list(s2)

    alist1.sort()
    alist2.sort()

    pos = 0
    matches = True
    while pos < len(s1) and matches:
        if alist1[pos] == alist2[pos]:
            pos = pos + 1
        else:
            matches = False

    return matches


def anagram_solution4(s1: str, s2: str) -> bool:
    """排序法改良版"""
    if len(s1) != len(s2):
        return False

    alist1 = list(s1)
    alist1.sort()  # O(n log(n))
    alist2 = list(s2)
    alist2.sort()  # O(n log(n))

    for k in range(0, len(alist1)):  # O(n)
        if alist1[k] != alist2[k]:
            return False

    return True


# def anagram_solution5(s1: str, s2: str) -> bool:
# 暴力法
# 生成s1中出现字符的全排列，再查看s2中是否出现在全排列中
# O(n!)
# pass


def anagram_solution6(s1: str, s2: str) -> bool:
    """计数比较法"""
    c1 = [0] * 26
    c2 = [0] * 26

    for i in range(len(s1)):  # O(n)
        pos = ord(s1[i]) - ord("a")
        c1[pos] = c1[pos] + 1

    for i in range(len(s2)):  # O(n)
        pos = ord(s2[i]) - ord("a")
        c2[pos] = c2[pos] + 1

    j = 0
    still_ok = True
    while j < 26 and still_ok:  # O(1)
        if c1[j] == c2[j]:
            j = j + 1
        else:
            still_ok = False

    return still_ok


def anagram_solution(s1: str, s2: str) -> bool:
    from collections import Counter

    """计数比较法 字典改造"""
    if len(s1) != len(s2):
        return False

    d1 = dict(Counter(s1))
    d2 = dict(Counter(s2))

    for k, v in d1.items():
        if v != d2.get(k, 0):
            return False

    return True
